﻿#include "stdafx.h"
#include "NextPermutation.h"

using namespace std;

namespace algorithm {
    void CNextPermutation::Next(std::vector<int>& nums)
    {
        // 先从右向左寻找第一个降序的索引
        int count = (int)nums.size();
        int left = -1;
        for (int i = count -1; i >= 0; i--) {
            if (i + 1 >= count) {
                continue;
            }
            if (nums[i] < nums[i + 1]) {
                left = i;
                break;
            }
        }
        if (left == -1) {
            // 未找到，当前已经是最大序列，返回最小序列
            sort(nums.begin(), nums.end());
            return;
        }
        // 从右向左寻找第一个大于left索引的值
        int right = -1;
        for (int i = count -1; i >= 0; i--) {
            if (nums[left] < nums[i]) {
                right = i;
                break;
            }
        }
        //if (right == -1) {
            // 不会发生，见left寻找逻辑
        //}
        // 交换
        swap(nums[left], nums[right]);
        // 从小到大排序left+1后的值，获得字典序最小增加的序列
        sort(nums.begin() + left + 1, nums.end());
    }
}
